#include<iostream>
#include<string>
using namespace std;

const int kMaxN = (int)1e6 + 10;
const int kCharacterSet = 26;

int f[kMaxN];
int g[kMaxN][kCharacterSet];

void Mod(int &x){
    const int kMod = 998244353;
    
    if(x < 0){
        x += kMod;
    }
    else if(x >= kMod){
        x -= kMod;
    }
} 

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    int T;
    
    for(cin >> T; T; T--){
        int n, k;
        string s;
        
        cin >> n >> k >> s;
        
        k = min(n - 1, k);
        fill(f, f + n, 0);
        for(int i = 0; i < k + 1; i++){
            fill(g[i], g[i] + kCharacterSet, 0);
            f[i] = 1;
            g[i][s[i] - 'a'] = 1;
            if(i){
                for(int j = 0; j < kCharacterSet; j++){
                    g[i][j] |= g[i - 1][j];
                }
            }
        }
        for(int i = k + 1; i < n; i++){
            fill(g[i], g[i] + kCharacterSet, 0);
            for(int j = 0; j < kCharacterSet; j++){
                g[i][j] = g[i-1][j];
                if(s[i] - 'a' == j){
                    f[i] = 1;
                    for(int c = 0; c < kCharacterSet; c++){
                        f[i] += g[i - k - 1][c];
                        Mod(f[i]);
                    }
                    f[i] -= g[i - 1][j];
                    Mod(f[i]);
                    g[i][j] += f[i];
                    Mod(g[i][j]);
                }
            } 
        }
        
        int ans = 0;
        
        for(int c = 0; c < kCharacterSet; c++){
            ans += g[n - 1][c];
            Mod(ans);
        }
        cout << ans << endl;
    }
    return 0;
}
